// class Solution {
// public:
//     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//         vector<int> v;
//         multiset<int> st;
//         map<int,int> mp;
//         for (int i = 0; i < k; i++){
//             st.insert(nums[i]);
//             mp[nums[i]]++;
//         }
//         v.push_back(*(--st.end()));
//         for (int i = k; i < nums.size(); i++) {
//             if(mp[nums[i-k]]==1){
//                 st.erase(nums[i-k]);
//             }
//             mp[nums[i-k]]--;
//             st.insert(nums[i]);
//             mp[nums[i]]++;
//             v.push_back(*(--st.end()));
//         }
//         return v;
//     }
// };

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> v;
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; i++) {
            q.push({nums[i], i});
        }
        v.push_back(q.top().first);
        for (int i = k; i < nums.size(); i++) {
            q.push({nums[i], i});
            while (q.top().second <= i - k) {
                q.pop();
            }
            v.push_back(q.top().first);
        }
        return v;
    }
};